package day04;

public class ArraySort {

	/**
	 * @param args
	 */
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		int[] arr = { 6, 7, 8, 4, 3, 1, 2 };
		printArray(arr); // 排序前
		//selectSort(arr);
		//bubbleSort(arr);
		//insertSort(arr);
		@SuppressWarnings("rawtypes")
		Comparable[] intArr = { 4, 45, 67, 8, 3, 1, 2, 78, -1};
		
		quickSort(intArr, 0, intArr.length-1);
		for (int i = 0; i < intArr.length; i++) {
			System.out.println(intArr[i]);
		}
		printArray(arr); // 排序前
	}

	/**
	 * 数组选择排序
	 * 原理：最值出现在头角标的位置
	 * @param arr
	 */
	public static void selectSort(int[] arr) {
		int len = arr.length;
		for (int i = 0; i < len - 1; i++) {
			for (int j = i + 1; j < len; j++) {
				if (arr[i] > arr[j]) {
					swap(arr, i, j);
				}
			}
		}
	}

	/**
	 * 冒泡排序
	 * 原理：相邻两个数进行比较，最值出现在最后面
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		int length = arr.length;
		for (int i = 0; i < length - 1; i++) {
			for (int j = 0; j < length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(arr, j, j + 1);
				}
			}
		}
	}

	
	/**
	 * @author wangbiao<br/>
	 *         email:785497344@qq.com
	 * @description 插入排序，升序排列
	 * @since 1.0.0
	 * @date 2013-7-18下午7:38:26
	 *
	 * @param arr
	 */
	public static void insertSort(int[] arr) {
		int len = arr.length;
		for (int i = 1; i < len; i++) {
			for (int j = i; j > 0; j--) {
				if (arr[j] < arr[j-1]) {
					swap(arr, j, j-1);
				} else {
					break;
				}
			}
		}
	}
	
	/**
	 * 快速排序（Quicksort）是对冒泡排序的一种改进。
	 * 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
	 * 其中一部分的所有数据都比另外一部分的所有数据都要小，
	 * 然后再按此方法对这两部分数据分别进行快速排序，
	 * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
	 * 快速排序不稳定，O(log(n))的额外空间，时间复杂度为O(nlog(n))，不是自适应的。
	 */
	
	/**
	 * @author wangbiao<br/>
	 *         email:785497344@qq.com
	 * @description 快速排序实现
	 * @since 1.0.0
	 * @date 2013-7-19下午11:36:04
	 *
	 * @param arr
	 * @param low
	 * @param high
	 */
	public static <T> void quickSort(Comparable<T>[] arr, int low, int high) {
		//枢纽元,一般以第一个元素为基准进行划分 
		int i = low;
		int j = high;
		if (low < high) {
			//从数组的两端向中间扫描
			Comparable<T> pointKey = arr[low];
			//进行扫描的指针i，j；i从左边开始，j从右边开始
			while(i < j) {
				@SuppressWarnings("unchecked")
				T key = (T) pointKey;
				while(i < j && arr[j].compareTo(key) > 0) {
					j--;
				}
				if (i < j) {
					//比枢纽元素小的元素移到左边
					arr[i] = arr[j];
					i++;
				}
				while (i < j && arr[i].compareTo(key) < 0) {
					i++;
				}
				if (i < j) {
					//比枢纽元素小的元素移到左边
					arr[j] = arr[i];
					j--;
				}
			}
			//枢纽元素移到正确的位置
			arr[i] = pointKey;
			//前半段因子进行递归排序
			quickSort(arr, low, i-1);
			//后半段因子进行递归排序
			quickSort(arr, i+1, high);
		}
	}
	
	/**
	 * 打印数组
	 * 
	 * @param arr
	 */
	public static void printArray(int[] arr) {
		int len = arr.length;
		System.out.print("[");
		for (int i = 0; i < len; i++) {
			if (i != len - 1) {
				System.out.print(arr[i] + ", ");
			} else {
				System.out.println(arr[i] + "]");
			}
		}
	}

	/**
	 * 置换数组元素的位置
	 * @param arr
	 * @param a
	 * @param b
	 */
	public static void swap(int[] arr, int a, int b) {
		arr[a] = arr[a] ^ arr[b];
		arr[b] = arr[a] ^ arr[b];
		arr[a] = arr[a] ^ arr[b];
	}

}
